import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-18
 * Time: 21:56
 */

class Node{
    public int key;
    public Node next;
    public Node(int key){
        this.key=key;
    }
}
public class MyHashSet {
    public Node [] set;
    private int usedSize;
    //默认的负载因子
    private static final double DEFAULT_LOAD_FACTOR=0.75;
    public MyHashSet() {
        this.set=new Node[10000];
    }

    public void add(int key) {
        //如果重复直接退出
        if(contains(key)){
            return;
        }

        Node node=new Node(key);
        int hashCode=key%this.set.length;
        //插入
        node.next=this.set[hashCode];
        this.set[hashCode]=node;
        this.usedSize++;

        //插入之后检查负载因子
        double loadFactor=(this.usedSize)/this.set.length;
        //如果大于负载因子,开始扩容,重新哈希
        if(loadFactor>DEFAULT_LOAD_FACTOR){
            Node[] newSet= Arrays.copyOf(this.set,this.set.length*2);
            for(int i=0;i<this.set.length;i++){
                Node cur=this.set[i];
                if(cur==null){
                    continue;
                }
                //节点换到新的哈希表中
                int newCode=cur.key%newSet.length;
                while(cur!=null){
                    Node next=cur.next;
                    cur.next=newSet[newCode];
                    newSet[newCode]=cur;
                    cur=next;
                }
            }
            //换新的哈希表
            this.set=newSet;
        }
    }

    public void remove(int key) {
        int hashCode=key%this.set.length;
        Node prev=null;
        Node cur=this.set[hashCode];
        if(cur==null){
            return ;
        }
        if(cur.key==key){
            this.set[hashCode]=cur.next;
            this.usedSize--;
            return;
        }
        while(cur!=null){
            if(cur.key==key){
                prev.next=cur.next;
                this.usedSize--;
                return;

            }else{
                prev=cur;
                cur=cur.next;
            }
        }

    }

    public boolean contains(int key) {
        int hashCode=key%this.set.length;
        Node cur=this.set[hashCode];
        while(cur!=null){
            if(cur.key==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
}
